COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	toughn[f85,jmc]		A tough nut for sequence extrapolators
C00012 ENDMK
C⊗;
toughn[f85,jmc]		A tough nut for sequence extrapolators

	Ever since the 1950s, occasional researchers have proposed
sequence extrapolation as a paradigm problem for AI.  The idea
perhaps arises from the philosophical notion that ones life is
characterized by a sequence of sensory information, and that
learning, including the development of science, consists of the
ability to predict future sense data from the past.

	The researchers who take this view proceed in two ways.
The empirical approach involves programs that attempt to induce
the law of formation of a sequence from an initial segment
of the sequence.  For sequences of numbers formed by a linear
rule or whose {\it n}th differences are constant, this is not
difficult.  One can then go on to mixtures of sequences formed
according to given rules.  The other approach is to develop a
theory of sequence extrapolation.  Some papers taking these
approaches include [Fredkin xxx], [Michie xxx], [Mycielski xxx]
and xxx.

	As a sample AI problem sequence extrapolation can be considered
on its own merits, but the object of this paper is to express
objections to its being considered as a paradigmatic AI problem.
I will express these objections by some general arguments and
by an example problem called ``Boxes and Roofs''.

	Imagine an organism or knowledge seeking program interacting
with the world.  If it is intelligent enough it will find out
something about the world from its experience.  While its
inputs are indeed a sequence of sense data, the regularities
of the real world have a quite different character than the
usual regularities of the law of formation of a sequence.
This is because the world consists of parts in interaction
with each other and the sequence of sense data contains only
a tiny part of the information contained in the sequence of
events in the world.  Moreover, what can be learned about the
world is not the sequence events but rather the properties
of some accessible objects and their interactions.  What
constitutes accessibility is quite complex.  Thus some of
the mutual interactions of distant galaxies are accessible
and some of the events taking place in our own brains are not.

	The general point is illustrated by the following boxes-and-roofs
 sequence extrapolation problem.  Imagine a sequence of
0s and 1s formed according to the following kind of rule.  A
particle moves with constant velocity in a rectangular room.
When it hits a wall it bounces with the angle of reflection
equal to the angle of incidence.  Besides bouncing off the
walls of the room, it can also bounce off any of a number of
rectangular boxes of varying sizes and varying locations in
the room.  Besides the boxes the room contains some rectangular
roofs.  When a particle goes under a roof, it is invisible from
above.  The sequence of 0s and 1s is formed by sampling once every
unit of time.  If the particle is visible from above at the
sampling instant, the value of the corresponding sequence element
is 1.  Otherwise, the value is 0.

	I contend that extrapolating a segment of such a sequence or
determining its law is more typical of the corresponding problem
for real world sensory information than are the mathematical
sequences that have been investigated in the literature.  It
still leaves out many of the complexities of the real world, but
it has the following virtues.

	1. The sequence of sensory information is epiphenomenal to
the bouncing particle, since the position of the particle isn't
given but only whether it is visible.

	2. The ``law of nature'' behind the observed phenomenon
will not be easy to figure out.  However, inferring that the
phenomenon is produced by a particle bouncing off boxes and hidden
by roofs is probably easier than many real scientific problems.

	3. No finite amount of observation gives complete information
about the situation even when the general law is known.  There may
always be additional small boxes or roofs that the particle has
not yet encountered.

	The largest sense in which the problem is oversimplified
is that it doesn't provide a possibility for experiment.  This could
be added by allowing an experimenter to performing an action at
any time depending on some parameters.  Initially unbeknownst to him
the action would correspond to adding an additional box or roof
of a size and position that depended on the parameters of the
action.  Part of the establishment of the boxes-and-roofs
model of the phenomenon would be establishing this interpretation
of the actions available to him.  Most likely, the possibility of
experiment would make the problem much easier, but experiment is
not part of the original sequence extrapolation literature.

	The problem could be made easier by including in the sequence
not merely whether the particle was visible but its $x$ or $y$
co-ordinate or both when it was visible.

	While the primary intention of this note is to criticize
simple sequence extrapolation or induction as an AI paradigm problem,
I also think some variant of the problem is actually worthwhile as
an AI target.  Here are some possible research topics.

	1. Assume the boxes-and-roofs model, and write a program
to locate whatever boxes and roofs can be located by a given
segment of experience.

	2. Write a more general program that doesn't know the
boxes-and-roofs model but can be told it as declarative information
and can then locate the boxes and roofs.

	3. Write a program that can actually infer the boxes-and-roofs
model.  It should be provided with the possibility of experiment.

	4. It might also be worthwhile to determine how hard the
different forms of the problem are for people.

This file is toughn[f85,jmc] at SU-AI.